package com.bee.剑指offer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class 两数之和 {


    /**
     * 正确解法
     *
     * 使用Map，处理
     * @param numbers 这个数组是无序的所以，不你使用二分查找
     * @param target
     */
    public static int[] twoSum2 (int[] numbers, int target) {
        int[] result = new int[2];
        if(numbers.length == 0) {
            return result;
        }
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            int search = target - numbers[i];
            if(map.containsKey(search)) {
                result[0] = map.get(search) + 1;  // 这个索引的值比 i小
                result[1] = i + 1;
            }
            map.put(numbers[i],i);
        }
        return result;
    }

    public static int[] twoSum (int[] numbers, int target) {
        int[] result = new int[2];
        if(numbers.length == 0) {
            return result;
        }
        for (int i = 0; i < numbers.length; i++) {
            int search = target - numbers[i];
            int flag = binarySearch(numbers, search);
            if(flag != -1) {
                if(i < flag) {
                    result[0] = i + 1;
                    result[1] = flag + 1;
                } else {
                    result[0] = flag + 1;
                    result[1] = i + 1;
                }
                return result;
            }
        }
        return result;
    }

    public static int binarySearch(int[] numbers, int target) {
        if(numbers.length== 0) {
            return -1;
        }
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int mid = (low + high)/2;
            if(numbers[mid] == target) {
                return mid;
            }
            if(numbers[mid] < target) {
                low = mid + 1;
            }
            if (numbers[mid] > target) {
                high = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ints = twoSum2(new int[]{3,2,4}, 6);
        System.out.println(Arrays.toString(ints));
    }
}
